import java.awt.Color;
import java.util.ArrayList;
import java.util.Stack;

import javax.swing.JOptionPane;

import info.gridworld.actor.Actor;
import info.gridworld.actor.Bug;
import info.gridworld.actor.Flower;
import info.gridworld.actor.Rock;
import info.gridworld.grid.Grid;
import info.gridworld.grid.Location;;


public class MazeBug extends Bug {
	// record next loc
	public Location next;
	// record last loc so that it can return when it reach a blind spot.
	public Location last;
	// the stack used to record the nodes of tree
	public Stack<ArrayList<Location>> crossLocation;
	// record the number of steps taken to reach the exit of the maze
	Integer stepCount;
	
	// judge the exit 
	public boolean isEnd = false;	
	// the prob of being chosen in each direction 
	private int[] prob = {1,1,1,1};
	// record the path out of the maze
	public Stack<Location> myWay = new Stack<Location>();
	
	public MazeBug() {
		// TODO Auto-generated constructor stub
		setColor(Color.GREEN);
	}
	
	
	/*
	 * Bug action fun
	 * Each step will add a little number of steps
	 * Show the number of steps when an exit is found
	 * */
	public void act() {
		if(stepCount == 0) {
			Location loc = this.getLocation();
			myWay.push(loc);
 		}
		
		if(isEnd == true) {
			String msg = stepCount.toString() + " steps";
			JOptionPane.showMessageDialog(null, msg);
		}else if (canMove()) {
			move();
		}else {
			goBack();
			stepCount++;
		}
	}

	// return the number of locations are valid
	public ArrayList<Location> getValid(Location loc) {
		int dir[] = {Location.NORTH, Location.EAST, Location.SOUTH, Location.WEST};
		
		Grid<Actor> grid = getGrid();
		if(grid == null) {			
			return null;
		}
		ArrayList<Location> valid = new ArrayList<Location>();
		Location adjacentLocation;
		Actor adjacentActor;
		// Determine the valid loc in the four directions
		for (int i = 0; i < 4; i++) {
			adjacentLocation = loc.getAdjacentLocation(dir[i]);
			if(grid.isValid(adjacentLocation)) {
				adjacentActor = grid.get(adjacentLocation);
				// the condition of Exit
				if (adjacentActor instanceof Rock && adjacentActor.getColor().equals(Color.RED)) {
					next = adjacentLocation;
					ArrayList<Location> Exit = new ArrayList<Location>();
					Exit.add(next);
					return Exit;
				}
				else if(adjacentActor == null) {
					valid.add(adjacentLocation);
				}
			}
		}
 		return valid;
	}
	
	public boolean canMove() {
		ArrayList<Location> valid = new ArrayList<Location>();
		valid = getValid(this.getLocation());
		if(valid.size() > 0) {
			return true;
		}
		return false;		
	}
	
	public void move() {
		Grid<Actor> grid = getGrid();
		if (grid == null) {
			return;
		}
		Location myLoc = this.getLocation();
		ArrayList<Location> valid = new ArrayList<Location>();
		valid = getValid(myLoc);

		// continue move
		if(valid.size() == 1) {
			next = valid.get(0);
			int direction = myLoc.getDirectionToward(next);
			prob[direction/90]++;
		}else {
			// if have not only one valid loc.
			int n = valid.size();
			int maxPro = 0;
			int proIndex = 0;
			int count = 0;
			int chose = 0;
			// chose the max probability direction
			for(Location l : valid) {
				int direction = myLoc.getDirectionToward(l);
				if(prob[direction/90] > maxPro) {
					proIndex = (int)direction/90;
					maxPro = prob[direction/90];
					chose = count;
				}
				count++;
			}
			
			double r = (double) (Math.random());
			// high probability choose high probability direction
			if(r < 0.618 && r >= 0) {
				next = valid.get(chose);
				prob[proIndex]++;
			}
			else {
				int ran = (int) (Math.random() * n);
				next = valid.get(ran);
				int direction = myLoc.getDirectionToward(next);
				prob[direction/90]++;
			}
		}
		
		if(grid.isValid(next)) {
			Actor actor = (Actor)grid.get(next);
			
			if(actor instanceof Rock && actor.getColor().equals(Color.RED)) {
				isEnd = true;
			}
			setDirection(getLocation().getDirectionToward(next));
			moveTo(next);
			stepCount++;
			myWay.push(next);
		} else {
			removeSelfFromGrid();
		}
			
		Flower flower = new Flower(getColor());
		flower.putSelfInGrid(grid, myLoc);
	}
	
	public void goBack() {
		Grid<Actor> grid = getGrid();
		if (grid == null) {
			return;
		}
		
		Location myLoc = this.getLocation();
		myWay.pop();
		last = myWay.peek();
		setDirection(getLocation().getDirectionToward(last));
		moveTo(last);
		int direction = last.getDirectionToward(myLoc);
		// the last direction decrease 1
		prob[direction/90]--;
		
		Flower flower = new Flower(getColor());
		flower.putSelfInGrid(grid, myLoc);
	}
}
